package com.dateConstruction._02_seqList;

public class SeqList<T> {
    
    // 顺序表元素个数
    public int n;
    
    // 对象数组存储顺序表的数据元素，保护成员
    protected Object[] element;

    // 指定element数组容量的最小值
    private static final int MIN_CAPACITY = 16;
    
    // 构造空表，length指定数组容量，若length < MIN_CAPACITY，则取最小值
    public SeqList(int length) {
        if (length < MIN_CAPACITY) {
            length = MIN_CAPACITY;
        }
        this.element = new Object[length];
        this.n = 0;
    }
    
    // 创建默认容量的空表，构造方法重载
    public SeqList() {
        this(MIN_CAPACITY);
    }
    
    // 构造顺序表，由values数组提供元素，忽略其中空对象
    public SeqList(T[] values) {
        // 创建2倍values数组容量的空表，若values == null，则抛出NullPointException空对象异常
        this(values.length * 2);
        // 复制非null的数组元素
        for (int i = 0; i < values.length; i++) {
            if (values[i] != null) {
                this.element[this.n++] = values[i];
            }
        }
    }
    
    // 判断是否为空，若为空，则返回true
    public boolean isEmpty() {
        return this.n == 0;
    }
    
    // 返回元素个数
    public int size() {
        return this.n;
    }
    
    // 若0 <= i < n，则返回第i个元素，否则返回null
    public T get(int i) {
        if (i >= 0 && i < this.n) {
            return (T)this.element[i];
        }
        return null;
    }
    
    // 若0 <= i < n且x != null，则设置第i个元素为x，否则抛出序号越界异常或空对象异常
    public void set(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x == null");
        }
        if (i >= 0 && i < this.n) {
            this.element[i] = x;
        } else {
            throw new IndexOutOfBoundsException(i + "");
        }
    }
    
    // 返回所有元素的描述字符串，形式为"(,)"。覆盖Object类的toString()方法。顺序表遍历算法
    public String toString() {
        // 返回类名
        String str = this.getClass().getName() + "{";
        // 执行T类的toString()方法，运行时异常
        if (this.n > 0) {
            str += this.element[0].toString();
        }
        for (int i = 1; i < this.n; i++) {
            str += ", " + this.element[i].toString();
        }
        return str + "}";
    }
    
    // 返回所有元素的描述字符串，次序从后向前，方法体省略
    public String toPreviousString() {
        return "";
    }
    
    // 插入x为第i个元素，x != null，返回插入元素序号。对i容错，若i < 0，则头插入；若i > 长度，则尾插入
    public int insert(int i, T x) {
        if (x == null) {
            return -1;
        }
        if (i < 0) {
            i = 0;
        }
        if (i >= this.n) {
            i = n;
        }
        Object[] sourse = this.element;
        if (this.n == this.element.length) {
            this.element = new Object[sourse.length * 2];
            for (int j = 0; j < i; j++) {
                this.element[j] = sourse[j];
            }
        }
        /*
        // 为什么反过来就会失败呢？因为引用不等同于拷贝，原数组改变，引用其数组，那么引用也改变，本质上还是只有这一个数组
        for (int j = i; j < this.n; j++) {
            this.element[j + 1] = sourse[j];
        }
        */
        for (int j = this.n; j >= i; j--) {
            this.element[j + 1] = sourse[j];
        }
        this.n++;
        this.element[i] = x;
        return i;
    }
    
    // 尾插入
    public int insert(T x) {
        return insert(this.n, x);
    }
    
    // 删除第i个元素，0 <= i < n，返回被删除元素，若i越界，则返回null。
    public T remove(int i) {
        if (i >= 0 && i < this.n) {
            Object temp = this.element[i];
            for (int j = i; j < this.n; j++) {
                this.element[j] = this.element[j+1];
            }
            this.element[this.n - 1] = null;
            this.n--;
            
            return (T)temp;
        }
        return null;
    }
    
    // 删除所有元素
    public void clear() {
        for (int i = 0; i < this.n; i++) {
            this.element[i] = null;
        }
        this.n = 0;
    }
    
    // 在this引用的顺序表中，顺序查找首个与key相等的元素，返回元素序号i，0 <= i < n；若查找不成功，则返回-1
    // key元素包含作为查找依据的关键字数据项，由T类的equals()方法确定对象是否相等
    // 若key == null，则Java抛出NullPointerException空对象
    public int search(T key) {
        for (int i = 0; i < this.n; i++) {
            if (this.element[i].equals(key)) {
                return i;
            }
        }
        return -1;
    }
    
    // 比较this对象与obj是否相等
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj instanceof SeqList<?>) {
            SeqList<T> list = (SeqList)obj;
            if (this.n == list.n) {
                for (int i = 0; i < this.n; i++) {
                    if (this.element[i] != list.element[i]) {
                        return false;
                    }
                }
                return true;
            }
        }
        return false;
    }
    
    // 深拷贝
    public SeqList(SeqList<? extends T> list) {
        this(list.element.length);
        for (int i = 0; i < list.n; i++) {
            element[i] = list.element[i];
            n++;
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试字符串构造方法：");
        String str[] = {"A", "B", "C", "D", "E", "F"};
        SeqList<String> list = new SeqList<String>(str);
        System.out.println(list);
        System.out.println("测试insert(int, T)方法：");
        System.out.println(list.insert(0, "G") + ", " + list);
        System.out.println("测试insert(T)方法：");
        System.out.println(list.insert("H") + ", " + list);
        System.out.println("测试remove(int)方法：");
        System.out.println(list.remove(1) + ", " + list);
        System.out.println("测试search(T)方法：");
        System.out.println(list.search("D"));
        System.out.println("测试equals(Object)方法：");
        String str2[] = {"A", "C", "D", "E", "F", "G"};
        SeqList<String> list2 = new SeqList<String>(str2);
        System.out.println(list2.toString() + ", " + list.equals(list2));
        System.out.println("测试深拷贝构造方法：");
        SeqList<String> list3 = new SeqList<String>(list2);
        System.out.println(list3);
    }

}
